package com.fr.lintcode;

public class Q1687 {

    /**
     * @param n: The param n means 2*n rectangular square.
     * @return: Return the total schemes.
     * 斐波拉契
     */
    public long getTotalSchemes(int n) {
        // Write your code here.
    	if(n == 1) {
    		return 1;
    	}else if(n == 2) {
    		return 2;
    	}
    	long dp[] = new long[n+ 1];
    	dp[1] = 1;
    	dp[2] = 2;
    	for(int i = 3; i <= n; i++) {
    		dp[i] = dp[i-1] + dp[i -2];
    	}
    	return dp[n];
    }

}
